package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-01 22:47
 */
public class Q53 {
    public int maxSubArray(int[] nums) {
        int sum = nums[0], max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if(sum < 0){
                sum = nums[i];
            }else{
                sum += nums[i];
            }

            if(max < sum){
                max = sum;
            }
        }
        return max;
    }

    /**
     * 分治法
     * @param nums
     * @return
     */
    public int maxSubArray2(int[] nums) {
        return maxSubArrayIndex(nums, 0, nums.length - 1);
    }

    public int maxSubArrayIndex(int[] nums, int left, int right) {
        if(right == left){
            return nums[left];
        }
        int cut = (left + right) / 2;

        int leftSum = maxSubArrayIndex(nums, left, cut);
        int rightSum = maxSubArrayIndex(nums, cut + 1, right);

        int maxL = 0;
        int maxR = 0;
        int leftSumTemp = 0;
        int rightSumTemp = 0;

        for (int i = cut - 1; i >= 0; i--) {
            leftSumTemp += nums[i];
            maxL = Math.max(maxL, leftSumTemp);
        }

        for (int i = cut + 1; i < nums.length; i++) {
            rightSumTemp += nums[i];
            maxR = Math.max(maxR, rightSumTemp);
        }

        return Math.max(maxL + nums[cut] + maxR, Math.max(leftSum, rightSum));
    }


    public static void main(String[] args) {
        System.out.println(new Q53().maxSubArray2(new int[]{-2,1,-3,4,-1,2,1,-5,4}));
    }
}
